package Sort;

import Stack.ArrayStack;
import org.junit.Test;
import sun.applet.Main;

/**
 * @author yyq
 * @create 2021-10-19 12:30
 * 基数排序
 * 首先确认最大值，即获得排序几轮
 * 其次 进行桶排序
 *
 */
public class RadixSort {
    public static void radixSort(int[] a){
        //获取待排序数组a中最大值
        int maxA=a[0];
        for (int i = 1; i < a.length; i++) {
            if(a[i]>maxA)
                maxA=a[i];
        }
        //获取最大值的位数
        int maxlength=(maxA+"").length();

        //创建桶bucket 利用空间换取时间
        int[][] bucket=new int[10][a.length+1];
        //bucket初始化 利用各个一维数组的 0 设为index 存放指针 指向下一个存放的位置
        for (int i = 0; i < bucket.length; i++) {
            bucket[i][0]=1;
        }
        //根据最大位数确定进几轮桶
        for (int i = 0; i < maxlength; i++) {
            int x= (int) Math.pow(10,i+1);
            int y= (int) Math.pow(10,i);
            //第一列获取个位 第二轮获取百位...
            for (int j = 0; j < a.length; j++) {
                //首先获取 个 十 百位置的数值
                //        0               1               2
                //234%10  4   234%100/10  3  234%1000/100 2
                // 34%10  4    34%100/10  3   34%1000/100 0
                //  4%10  4     4%100/10  0    4%1000/100 0
                //确定数值
                int temp=0;
                temp=a[j]%x/y;
                //放入对应的桶中
                bucket[temp][bucket[temp][0]]=a[j];
                bucket[temp][0]++;
            }

            //经过一轮的放入 此时取出桶中的数据
            int index=0;
            for (int i1 = 0; i1 < bucket.length; i1++) {
                for (int i2 = 1; i2 <bucket[i1][0]; i2++) {
                    a[index]=bucket[i1][i2];
                    index++;
                }
            }
            //清空桶
            for (int z = 0; z < bucket.length; z++) {
                bucket[z][0]=1;
            }
        }
    }
    @Test
    public void test(){
        int[] a={213,2,23};
        radixSort(a);
        for (int i : a) {
            System.out.println(i);
        }
    }

}
